package symmetrictree

import "../binarytree"

// import "encoding/binary"

type TreeNode = binarytree.TreeNode


// 检查二叉树是否轴对称
func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return compare(root.Left, root.Right)
}

func compare(left, right *TreeNode) bool{
	// 首先排除空节点的情况
	if left == nil && right != nil {
		return false
	}else if left != nil && right == nil {
		return false
	}else if left == nil && right == nil {
		return true
	}else if left.Val != right.Val {// 排除了空节点，再排除数值不相同的情况
		return false
	}

	// 此时就是：左右节点都不为空，且数值相同的情况
	// 此时才做递归，做下一层的判断
	outside := compare(left.Left, right.Right);   // 左子树：左、 右子树：右
	inside := compare(left.Right, right.Left);    // 左子树：右、 右子树：左
	isSame := outside && inside;                    // 左子树：中、 右子树：中 （逻辑处理）
	return isSame;

}


// 迭代方法
func isSymmetricNon(root *TreeNode) bool {
	if root==nil {
		return true
	}
	// 根左右节点入栈 不判断是否为nil
	q := []*TreeNode{}
	q = append(q, root.Left)
	q = append(q, root.Right)
	var lnode,rnode *TreeNode  
	for len(q)!=0 {
		lnode = q[0]
		q = q[1:]  //出队
		rnode = q[0]
		q = q[1:]

		if !lnode && !rnode { // 皆空
			continue    //对称
		}

		// 有一个不为空 不对称
		if !lnode || !rnode || lnode.Val!=rnode.Val {
			return false
		}

		q = append(q, lnode.Left)
		q = append(q, rnode.Right)   // 让需要比较的成对进入

		q = append(q, lnode.Right)
		q  = append(q, rnode.Left)
	}
	return true
}